import java.awt.Point;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.PriorityQueue;

public class MeetingSolver {
	int numberOfMeetings;
	int numberOfEmployees;
	int numberOfTimeSlots;

	// array to store which meetings an employee must attend
	// meetingConstraintList[0] refers to the constraints of employee 1
	int[][] meetingConstraintLists;

	// array to store travel times between meetings
	// travelTimeLists[0][5] is the travel time from meeting 1 to 6
	int[][] travelTimeLists;
	
	PriorityQueue<PointC> mostAttendedMeetings;

	public MeetingSolver(String fileName) {
		BufferedReader br = null;
		try {
			String currentLine;
			br = new BufferedReader(new FileReader(fileName));
			// read in the txt file line by line, 
			while((currentLine = br.readLine()) != null) {
				//Check the current line to see what input we are dealing with
				if(currentLine.indexOf("of meetings") > 0){
					numberOfMeetings = Integer.parseInt(currentLine.split(" ")[3]);
				}
				if(currentLine.indexOf("of employees") > 0){
					numberOfEmployees = Integer.parseInt(currentLine.split(" ")[3]);
				}
				if(currentLine.indexOf("of time") > 0){
					numberOfTimeSlots = Integer.parseInt(currentLine.split(" ")[4]);
				}
				
				if(currentLine.indexOf("must attend") > 0){
					PointC[] meetingFreq = new PointC[numberOfMeetings];
					for(int i =0; i< meetingFreq.length; i++){
						meetingFreq[i] = new PointC();
						meetingFreq[i].y = i;
					}
					ArrayList<String> lists = new ArrayList<String>();
					//figure out how many lines we have
					while(!(currentLine = br.readLine()).equals("")){
						lists.add(currentLine);
					}
					meetingConstraintLists = new int[numberOfEmployees][];
					for(int i =0; i< lists.size(); i++){
						//split on whitespace
						String[] listInputs = lists.get(i).split(": ")[1].split("\\s+");
						meetingConstraintLists[i] = new int[listInputs.length];
						for(int j =0;j<listInputs.length;j++){
							meetingFreq[Integer.parseInt(listInputs[j])-1].x +=1;
							meetingConstraintLists[i][j] = Integer.parseInt(listInputs[j]);
						}
					}
					//keep track of the most restricted meetings so we know which order to try in
					mostAttendedMeetings = new PriorityQueue<PointC>();
					for(int i =0; i< meetingFreq.length; i++)
						mostAttendedMeetings.add(meetingFreq[i]);
				}
				
				if(currentLine.indexOf("between meetings") > 0){
					ArrayList<String> lists = new ArrayList<String>();
					//skip the first line since it has no usefull info
					br.readLine();
					//figure out how many lines we have
					while((currentLine = br.readLine()) != null){
						lists.add(currentLine);
					}
					travelTimeLists = new int[lists.size()][];
					for(int i =0; i< lists.size(); i++){
						//split on whitespace
						String[] listInputs = lists.get(i).split(":")[1].split("\\s+");
						travelTimeLists[i] = new int[listInputs.length];
						for(int j =1;j<listInputs.length;j++){
							travelTimeLists[i][j-1] = Integer.parseInt(listInputs[j]);
						}
					}
				}
			}
		} catch (IOException e) {
			e.printStackTrace();
		} finally {
			try {
				if (br != null)
					br.close();
			} catch (IOException ex) {
				ex.printStackTrace();
			}
		}
	}
	int comparisonCount = 0;
	public void solveMeetings(){
		ArrayList<Integer> meetings = new ArrayList<Integer>();
		for(int i =0; i< numberOfMeetings; i++){
			meetings.add(mostAttendedMeetings.remove().y);
		}
		System.out.println(meetings);
		ArrayList<ArrayList<Integer>> meetingTimes = new ArrayList<ArrayList<Integer>>();
		for(int i =0; i < numberOfTimeSlots; i++){
			meetingTimes.add(new ArrayList<Integer>());
		}
		comparisonCount =0;
		solveMeetings(meetingTimes, meetings);
		System.out.println("Comparisons: "+comparisonCount);
	}
	
	private boolean solveMeetings(ArrayList<ArrayList<Integer>> meetingTimes, ArrayList<Integer> meetings){
		if(meetings.size() == 0){
			for(int i=0; i<numberOfTimeSlots; i++){
				for(int j =0; j < meetingTimes.get(i).size(); j++)
					System.out.println("Meeting " + (meetingTimes.get(i).get(j)+1) + " is schedueled at time "+ (i+1));
			}
			return true;
		}
		int currMeeting = meetings.remove(0);
		//try to schedule a meeting at every time slot
		for(int i=0;i<numberOfTimeSlots; i++){
			comparisonCount += 1;
			if(isAssignmentValid(meetingTimes, currMeeting, i)){
				meetingTimes.get(i).add(currMeeting);
				if(solveMeetings(meetingTimes, new ArrayList<Integer>(meetings))){
					//we Found a solution stop checking
					return true;
				}
				//remove from the array so that we never assigned currMeeting
				meetingTimes.get(i).remove(meetingTimes.get(i).size()-1);
			}
		}
		return false;
	}
	
	//given the constrained meeting times and an attempted meeting assignment 
	//check if all employees that need to can make the meeting
	private boolean isAssignmentValid(ArrayList<ArrayList<Integer>> meetingTimes,
			int currMeeting, int assignment) {
		for(int i =0; i < numberOfEmployees; i++){
			for(int j=0; j < meetingConstraintLists[i].length; j++){
				//check all the employees that have to go to a meeting we schedueld
				if(meetingConstraintLists[i][j] == (currMeeting+1)){
					for(int k=0; k < meetingConstraintLists[i].length ; k++){
						if(meetingConstraintLists[i][k] != (currMeeting+1)){
							int travelTime = travelTimeLists[currMeeting][meetingConstraintLists[i][k]-1];
							//check if we have assigned i before if we have and we dont have enough time return false
							for(int l=0; l < numberOfTimeSlots; l++){
								if(meetingTimes.get(l).contains(meetingConstraintLists[i][k]-1)){
									if(Math.abs(assignment-l) <= (travelTime)){
										return false;
									}
								}
							}
						}
					}
				}
			}
		}
		return true;
	}
	public class PointC extends Point implements Comparable{

		@Override
		public int compareTo(Object arg0) {
			// TODO Auto-generated method stub
			if (this.x > ((PointC)arg0).x)
				return 0;
			return 1;
		}
		
	}
	public static void main(String[] args){
		MeetingSolver s1 = new MeetingSolver("problem3.txt");
		s1.solveMeetings();
	}
}
